package LeetCode.Leet1_99.Leet50_59.Leet56;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @ClassName Solution_1
 * @Author 孙天赐
 * @Date 2025/6/4 8:26
 * @Description TODO: 方法一   模拟（贪心）  7ms 89.04%
 */
class Solution {
    public int[][] merge(int[][] intervals) {
        // 按照区间起点升序排序，起点相同则按照终点升序排序
        Arrays.sort(intervals, (o1, o2) -> {
            if (o1[0] != o2[0]) {
                return o1[0] - o2[0];
            } else {
                return o1[1] - o2[1];
            }
        });

        List<int[]> list = new ArrayList<>();
        // 左边界最小值
        int left = intervals[0][0];
        // 右边界的最大值
        int right = intervals[0][1];
        // 不断记录右边界的最大值，当当前左边界超过了记录的右边界最大值，说明左侧记录的区间与后面区间不再重叠
        // 则合并左边界最小值和右边界的最大值之间的区间
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] > right) {
                // 合并区间
                list.add(new int[]{left, right});
                left = intervals[i][0];
                right = intervals[i][1];
            } else {
                right = Math.max(right, intervals[i][1]);
            }
        }
        // 加入最后一个
        list.add(new int[]{left, right});

        int[][] result = new int[list.size()][2];
        for (int i = 0; i < result.length; i++) {
            result[i] = list.get(i);
        }
        return result;
    }
}
